package com.captain.leetcode.二分查找;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/3/20 21:39
 */
public class 在排序数组中查找元素的第一个和最后一个位置34 {

    public int[] searchRange(int[] nums, int target) {
        //1 获取第一个
        int first = getFirst(nums, target);
        int last = getLast(nums, target);
        return new int[]{first, last};
        //2.获取最后一个
    }

    /**
     * des:
     * 获取第一个
     *
     * @author captain
     * @date 2022/3/20 21:40
     */
    private int getFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            //0 - 100  40
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                //mid == 0 , 第一个 / 前一个不相等
                if ((mid == 0) || (nums[mid - 1] != target)) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * des:
     * 获取最后一个
     *
     * @author captain
     * @date 2022/3/20 21:40
     */
    private int getLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            //0 - 100  40
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                //mid == 0 , 第一个 / 前一个不相等
                if ((mid == nums.length - 1) || (nums[mid + 1] != target)) {
                    return mid;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}
